Benchmark Instances for the Travelling Salesman Problem with Time Windows (TSPTW)

Manuel López-Ibáñez and Christian Blum.

Introduction

This is the collection of benchmark instances used in our papers Beam-ACO for the travelling salesman problem with time windows [1] and The Travelling Salesman Problem with Time Windows: Adapting Algorithms from Travel-time to Makespan Optimization [10]. These instances are available from different sources, sometimes along with instructions on how to modify them to match previous results. Here we provide them all together in a single place, and converted them into a standard format.

The format of the instances is as follows:

  1. Number of nodes (including the depot).
  2. Distance matrix. The first row is the distance from the depot to the other nodes. The first column is the distance from the other nodes to the depot. This distance typically represents the travel time between nodes i and j, plus the service time at node i, if one is given in the original instance. The distance matrix is not necessarily symmetrical.
  3. Time windows (earliest, latest) for each node, one per line. The first node is the depot.
  4. Optional comments prefixed by # that provide non-essential information, for example, the sum of service times. Results reported by us already include the sum of service time in the final objective value. If you wish to recover the objective values without service times, for example, previous works may report results that do not include it, just subtract the sum of service times from the values in the tables below.

Relevant Literature

[1]
Manuel López-Ibáñez and Christian Blum. Beam-ACO for the travelling salesman problem with time windows. Computers & Operations Research, 37(9):1570-1583, 2010. doi: 10.1016/j.cor.2009.11.015
[ Instances | Best-known solutions for this paper ]
(The results of CA mentioned here correspond to a pre-print version of Ohlmann and Thomas [7], but they differ only slightly from the results published by INFORMS.)
[2]
J.-Y. Potvin and S. Bengio. The vehicle routing problem with time windows part II: Genetic search. INFORMS Journal on Computing, 8:165-172, 1996.
[3]
M. M. Solomon. Algorithms for the vehicle routing and scheduling problems with time windows. Operations Research, 35:254-265, 1987.
[4]
A. Langevin, M. Desrochers, J. Desrosiers, Sylvie Gélinas, and F. Soumis. A two-commodity flow formulation for the traveling salesman and makespan problems with time windows. Networks, 23(7):631-640, 1993.
[5]
Y. Dumas, J. Desrosiers, E. Gelinas, and M. M. Solomon. An optimal algorithm for the traveling salesman problem with time windows. Operations Research, 43(2):367-371, 1995.
[6]
M. Gendreau, A. Hertz, G. Laporte, and M. Stan. A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 46:330-335, 1998.
[7]
Jeffrey W. Ohlmann and Barrett W. Thomas. A compressed-annealing heuristic for the traveling salesman problem with time windows. INFORMS Journal on Computing, 19(1):80-90, 2007.
[8]
N. Ascheuer. Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems. PhD thesis, Technische Universität Berlin, Berlin, Germany, 1995.
[9]
G. Pesant, M. Gendreau, J.-Y. Potvin, and J.-M. Rousseau. An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transportation Science, 32:12-29, 1998.
[10]
Manuel López-Ibáñez, Christian Blum, Jeffrey W. Ohlmann, and Barrett W. Thomas. The Travelling Salesman Problem with Time Windows: Adapting Algorithms from Travel-time to Makespan Optimization. Applied Soft Computing, 13(9):3806–3815, 2013.
[11]
Khalid Amghar, Jean-François Cordeau, Bernard Gendron. A General Variable Neighborhood Search Heuristic for the Traveling Salesman Problem with Time Windows under Completion Time Minimization.
[12]
G. Björdal, P. Flener, J. Pearson, P. J. Stuckey, and G. Tack. Solving satisfaction problems using large-neighbourhood search. CP 2020, LNCS, volume 12333, pages 55-71, 2020.
[13]
R. Ferreira da Silva and S. Urrutia. A general VNS heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7(4):203-211, 2010.
[14]
Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck. Sequence Variables for Routing Problems. 28th International Conference on Principles and Practice of Constraint Programming (CP 2022), 2022.
[15]
Xavier Gillard, Pierre Schaus. Large Neighborhood Search with Decision Diagrams. International Joint Conference on Artificial Intelligence (IJCAI 2022), 2022.
[16]
Isaac Rudich, Quentin Cappart, and Louis-Martin Rousseau. Improved peel-and-bound: Methods for generating dual bounds with multivalued decision diagrams. Journal of Artificial Intelligence Research, 77:1489,1538, 2023.
[17]
Kuroiwa, R. and Beck, J.C., Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization, Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS2023), 2023.
[18]
Kuroiwa, R. and Beck, J.C., Solving Domain-Independent Dynamic Programming Problems with Anytime Heuristic Search, Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS2023), 2023.
[19]
Fontaine, R., Dibangoye, J., and Solnon, C. (2023). Exact and anytime approach for solving the time dependent traveling salesman problem with time windows. European Journal of Operational Research, 311(3), 833-844.
[20]
Ryo Kuroiwa and J. Christopher Beck. Beam Search Algorithms for Domain-Independent Dynamic Programming. Proceedings of the Thirty-Eighth Annual AAAI Conference on Artificial Intelligence (AAAI2024), 2024.
[21]
Baldacci, R., Mingozzi, A., and Roberti, R. New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS Journal on Computing,24(3), 356-371, 2012.

Benchmark Instances

SolomonPotvinBengio
30 asymmetric instances originally provided by Potvin & Bengio [2] and derived from Solomon's RC2 VRPTW instances [3]. These instances are very diverse in structure. The number of customers (n) ranges from 3 to 44 customers.
Langevin
Seven instance classes of 10 instances each provided by Langevin et al. [4]. Instances are grouped by number of customers and time window width. NOTE: These instances are trivial to solve nowadays and most optimisers solve them in less than 1 second. They should not be used for new benchmarking studies.
Dumas
27 symmetric classes of five instances each. All instances were proposed and solved to optimality by Dumas et al. [5]. Instance size ranges from 20 to 200 customers.
GendreauDumasExtended
130 symmetric instances grouped into 26 classes with equal number of customers and time window width provided by Gendreau et al. [6]. These instances were obtained from the instances proposed by Dumas et al. [5] by extending the time windows by 100 units, resulting in time windows in the range from 120 to 200 time units.
OhlmannThomas
25 symmetric instances grouped into five classes proposed by Ohlmann & Thomas [7]. The instances were derived from the instances with 150, respectively 200, customers proposed by Dumas et al. [5] by extending the time windows by 100 time units.
AFG (rbg)
50 asymmetric TSPTW instances introduced by Ascheuer [8]. These are real-world instances derived from an industry project with the aim to minimize the unloaded travel time of a stacker crane within an automated storage system. We have removed instance rbg021.tw because it is exactly the same as rbg019c.tw.
SolomonPesant
27 asymmetric instances proposed by Pesant et al. [9]. While they were derived from Solomon's RC2 VRPTW instances [3], they are different from the instances proposed by Potvin & Bengio [2].

NOTE: The original SolomonPotvinBengio, Langevin, Dumas, GendreauDumasExtended and OhlmannThomas instances can be obtained from Ohlmann & Thomas. The original AFG instances are provided by the Konrad-Zuse-Zentrum für Informationstechnik Berlin. The original SolomonPesant instances were provided by Andrea Tramontani in personal communication.

Best-known solutions for travel time objective

NOTE: The best-known solutions reported here are not necessarily the ones reported in our papers [1] [10] above. Since those papers were published, we may have become aware of a better best-known solution for some instances. The purpose of these tables is to give an idea of how far from near-optimal a solution might be and also to allow others to verify the solutions they obtain (if they match the best-known). If you think you have found a new best-known solution (or solved the instances to optimality), please let us know, so we can update the table and take it into account in future research.

2020/9/24: Due to a rounding error, the best-known traveltime of a few instances in GendreauDumasExtended was wrong by a few units. This prompted me to verify all solutions from all instances and, as far as I can tell, they are correct. Thanks to Gustav Björdal from Uppsala University for reporting the problem.

2020/9/25: Björdal et al. (2020) published updated best-known solutions for several GendreauDumasExtended instances.

2022/7/1: Gillard and Schaus (2022) published updated best-known solutions for several OhlmannThomas and AFG instances.

2022/7/1: Using Beam-ACO and GVNS, Manuel López-Ibáñez replaced infeasible best-known solutions of various Dumas instances with feasible ones. Now all best-known solutions reported for Dumas are feasible ones. In addition, new best-known solutions for almost all OhlmannThomas instances were generated using GVNS.

2022/7/8: Delecluse et al. (2022) reported improved best-known solutions for 9 AFG instances and 1 GendreauDumasExtended instance. The latter is also found by GVNS in less than a second.

2022/11/7: New best-known solutions for 7 AFG instances were found by LocalSolver 11.5.

2023/02/20: Isaac Rudich has kindly provided a table of bounds and optimality gaps showing which best-known solutions are optimal and which ones remain open.

2023/03/02: Ryo Kuroiwa has provided the optimal solution of instance rbg132.2.tw and new best-known for rbg193.2.tw and proven the optimality of a few other best-known solutions.

2023/12/30: Ryo Kuroiwa has provided new best-known solutions for instances rbg193.2.tw, which corresponds to the known optimal value, and rbg233.2.tw.

2023/12/30: I detected several issues in the file Bounds and optimality gaps and revised its contents. In particular, some optimal solutions reported by Baldacci et al. (2012) are wrong (probably due to recreating the instances instead of using the canonical instances provided here). Baldacci et al. (2012) reported optimal solutions for all instances except one. However, without a verified permutation available that matches the reported optimal value, I consider those values to be lower bounds.

Bounds and optimality gaps (all instances)
SolomonPotvinBengio
Langevin
Dumas
GendreauDumasExtended
OhlmannThomas
AFG (rbg)
SolomonPesant

Best-known solutions for makespan objective

NOTE: The best-known solutions reported here are not necessarily the ones reported in our papers [1] [10] above. Since those papers were published, we may have become aware of a better best-known solution for some instances. The purpose of these tables is to give an idea of how far from near-optimal a solution might be and also to allow others to verify the solutions they obtain (if they match the best-known). If you think you have found a new best-known solution (or solved the instances to optimality), please let us know, so we can update the table and take it into account in future research.

NOTE #2: Some instances available above are missing from the tables below. The reason is that we never tested those instances in our paper [10] because previous studies did not consider them. If you find a very good solution for them, we will happy add them to the tables after verifying them.

2018/08/18: Andy Doucette (2018) reported best-known solutions for Langevin instances. Amghar, Cordeau and Gendron also reported these solutions in 2017 at IFORS. In fact, these instances were evaluated by [10] but solutions were never reported because the instances are trivial to solve by all modern solvers (including Beam-ACO and CSA) within 1 CPU-second. Thus, there is a very high probability that these are the optimal solutions.

2018/10/22: Amghar, Cordeau and Gendron (2019) published best-known solutions for previously unreported instances.

2023/02/20: Isaac Rudich has kindly provided a table of bounds and optimality gaps showing which best-known solutions are optimal and which ones remain open.

2023/10/11: Fontaine et al. (2023) have proven the optimality of 7 out of the 12 instances that remain open.

Bounds and optimality gaps (all instances)
SolomonPotvinBengio
Langevin
Dumas
GendreauDumasExtended
OhlmannThomas
AFG (rbg)
SolomonPesant

Example Source Code

The following program reads an instance file and a file with a permutation (from 1 to n, that is, not containing the depot) and evaluates the permutation according to the instance. The function Solution::LoadInstance is an example of how to read an instance file following the standard format described in the introduction.

[ Download check_solution.cpp ]

In GNU/Linux, the following commands executed in the shell demonstrate the use of the solution checker:

 g++ -o check_solution check_solution.cpp
 wget http://lopez-ibanez.eu/files/TSPTW/SolomonPotvinBengio.tar.gz
 tar xvf SolomonPotvinBengio.tar.gz
 echo "13 14 18 4 9 5 7 8 6 16 19 17 1 11 3 12 10 2 15" > bestsol-rc_201.1.txt
 ./check_solution SolomonPotvinBengio/rc_201.1.txt bestsol-rc_201.1.txt

The last line above prints:

 makespan = 592.06       tourcost = 545.33       constraint violations = 0

which is the same makespan that you can find in the corresponding file above (I used the best-known permutation for makespan).